§1.1 Field of the Invention
The present invention concerns logic optimization. More specifically, the present invention concerns optimizing classifiers, such as classifiers encoded onto a ternary content addressable memory (“TCAM”) for example.
§1.2 Background Information
§1.2.1 Packet Classification and TCAMs
Packet classification has been used as a basic building block in many network applications such as quality of service (“QoS”), flow-based routing, firewalls, and network address translation (“NAT”). (See, e.g., D. E. Taylor, “Survey and taxonomy of packet classification techniques,” ACM Computer Surveys, pp. 238-275, 2005; and Y. Xu, Z. Liu, Z. Zhang, H. J. Chao, “An Ultra High Throughput and Memory Efficient Pipeline Architecture for Multi-Match Packet Classification without TCAMs”, ACM/IEEE ANCS, 2009, both incorporated herein by reference.) In packet classification, information is extracted from the packet header and compared against a classifier consisting of a list of rules. Once an incoming packet matches some rules, it will be processed based on the action associated with the highest-priority matched rule. The table 100 of FIG. 1 illustrates a sample classifier with three rules (R1-R3) 110. Each of the three rules 110 specifies a pattern of five fields; namely, source Internet Protocol (“IP”) (prefix) 120, destination IP (prefix) 130, source port (range) 140, a destination port (range) 150, and protocol type 160. From the geometric point of view, each rule can be viewed as a hyper-rectangle (also referred to a “block” in this application) in the 104-dimensional Boolean Space, corresponding to the 104 bits in the five fields.
TCAM has been widely used to implement packet classification because of its parallel search capability and constant processing speed. A TCAM has a massive array of entries (See, e.g., K. Pagiamtzis and A. Sheikholeslami, “Content-addressable memory (CAM) circuits and architectures: A tutorial and survey,” IEEE Journal of Solid-State Circuits, vol. 41, no. 3, pp. 712-727, March 2006, incorporated herein by reference.), in which each bit can be represented in either ‘0’, ‘1’, or “*” (wildcard). Before a rule can be stored in TCAMs, its range fields are converted to prefixes. For example, rule R2 110 of FIG. 1 requires only one TCAM entry since it contains only prefix fields. However, for rule R1, both the source port 140 and destination port 150 contain a range [1, 5]. Consequently, both of them need to be expanded to three prefixes, i.e., “001” (corresponding to “1”), “01*” (corresponding to “2” and “3”), and “10*” (corresponding to “4” and “5”). The combination of the prefix specifications of the two ranges for source port 140 and destination port 150 will consume 9 (=3×3) TCAM entries. This simple example illustrates the well-known “range expansion” problem. (Hereafter, assume that all the classifiers used in examples have already been expanded to prefixes, and no longer contain ranges.) Since TCAMs not only expensive, but also power-hungry, the range expansion problem heavily increases not only the manufacturing cost, but also the operation cost of network equipment provided with TCAMs.
§1.2.2 The Need for TCAM Entry Reduction
Given the expense and power consumption of TCAMs, it is very desirable to reduce the TCAM entries that are required to represent a classifier. Previous work in this field can be classified into three categories; namely, hardware improvement, range encoding, and classifier compression. Each of these three categories of TCAM entry reduction is introduced below.
First, approaches in the category of TCAM hardware improvement require modifications in the TCAM hardware to directly support range matching. For example, there have been attempts to directly compare ranges by introducing a two-level hardware hierarchy and incorporating special range comparison circuits into TCAM arrays. (See, e.g., E. Spitznagel, D. Taylor, and J. Turner, “Packet classification using extended tcams,” IEEE ICNP, 2003, incorporated herein by reference.)
Second, most research to resolve the range expansion problem falls into the category of range encoding. (See, e.g., A. Bremler-Barr and D. Hendler, “Space-Efficient TCAM-based Classification Using Gray Coding,” IEEE INFOCOM, 2007; A. Bremler-Barr, D. Hay and D. Hendler, “Layered Interval Codes for TCAM-based Classification,” IEEE INFOCOM, 2009; M. Bando, N. S. Artan, R. Wei, X. Guo and H. J. Chao, “Range Hash for Regular Expression Pre-Filtering,” ACM/IEEE ANCS, 2010; C. R. Meiners, A. X. Liu and E. Torng, “Topological Transformation Approaches to Optimizing TCAM-Based Packet Classification Systems,” SIGMETRICS, 2009, 0. Rottenstreich and I. Keslassy, “Worst-Case TCAM Rule Expansion,” IEEE INFOCOM, 2010, each of which is incorporated by reference.) With range encoding, each range field in the rules is represented by a unique binary code, which can be directly stored in TCAMs without causing range expansion. Although the range encoding can avoid range expansion, it requires a separate range searching on each non-prefix dimension before looking up the TCAMs.
Finally, in the category of classifier compression, approaches proposed by Draves (See, e.g., R. Draves, C. King, S. Venkatachary, and B. Zill, “Constructing optimal IP routing tables,” Proceedings of IEEE INFOCOM, 1999, incorporated herein by reference.) and Suri (See, e.g., S. Suri, T. Sandholm, and P, “Warkhede. Compressing two-dimensional routing tables,” Algorithmica, Vol. 35, pp. 287-300, 2003, incorporated herein by reference.) attempted to compress IP routing tables in TCAMs, which actually are special classifiers with only one field. Recent research on classifier compression (See, e.g., Q. Dong, S. Banerjee, J. Wang, D. Agrawal, and A. Shukla, “Packet classifiers in ternary CAMs can be smaller,” SIGMETRICS, 2006; A. X. Liu, E. Torng, and C. Meiners, “Firewall compressor: An algorithm for minimizing firewall policies,” INFOCOM, 2008; and R. McGeer and P. Yalagandula, “Minimizing Classifiers for TCAM Implementation,” Proceedings of IEEE INFOCOM, 2009, each of which is incorporated herein by reference.) aim to convert the original classifiers to “semantically equivalent” classifiers that consume fewer TCAM entries.
§1.2.3 Limitations of Known Classifier Compression-Based TCAM Entry Reduction
Previously-proposed schemes for classifier compression share a common objective (that is, to find a smaller and semantically equivalent classifier). Such schemes take advantage at least one of two properties; namely that rules are normally “action oriented” and rules following a “first matching” rule can be ignored. Each of these properties, which may be exploited for classifier compression, is introduced below.
First, regarding the fact that rules are often action-oriented, in packet classification, the action associated with a matched rule is often of paramount importance; the ID associated with the matched rule is typically not important. Therefore, a classifier can be modified as long as the modification doesn't change the action returned by each classification operation. Consider FIG. 2(a) for example. Rules R1 and R2 can be merged into R4. Although the rules have been changed, the compressed classifier at the right is still equivalent to the original classifier on the left because the compressed classifier can still report the same action as the original classifier.
Second, regarding the first-matching property, when multiple rules match the same packet, TCAM only reports the first matched rule. FIGS. 2 (b) and 2(c) are two examples showing how to compress a classifier using the first-matching property. More specifically, in FIG. 2(b), because R2 is completely covered by R1, any packet matching R2 will definitely match R1. Consequently, R2 is a redundant rule and removing it will not affect the packet classification results. In FIG. 2(c), R1, R2 and R3 cannot be directly merged. However, by adding R0, these rules can be merged with R0 into a single rule R6. The one problem is that this would result in a non-equivalent classifier, because R0 forces the action of “0000” to be “Accept” even though it is “Deny” in the original classifier. To make the classifiers equivalent, R5 is added above (i.e., before) R0. Due to the first-matching property, R0 will be blocked by R5, and the compressed classifier of FIG. 2(c) is equivalent to the original classifier of FIG. 2(c).
Using the “action-oriented” and “first-matching” properties, Dong et al. proposed four simple heuristic algorithms, called Trimming, Expanding, Adding and Merging, to find the equivalent classifiers consuming fewer TCAM entries. (See, e.g., Q. Dong, S. Banerjee, J. Wang, D. Agrawal, and A. Shukla, “Packet classifiers in ternary CAMs can be smaller,” SIGMETRICS, 2006, incorporated herein by reference.) Each heuristic algorithm works well for some certain scenarios. Dong's approach recursively searches a classifier to explore if any of these four heuristics can be applied to reduce rules. Liu et al. proposed an algorithm to compress the firewall classifiers. (See, e.g., A. X. Liu, E. Torng, and C. Meiners, “Firewall compressor: An algorithm for minimizing firewall policies,” INFOCOM, 2008, incorporated herein by reference.) In the Liu et al. algorithm, ranges in the original classifier are first decomposed into non-overlapping ranges. Then, gaps between the non-overlapping ranges are filled to reduce the number of rules. Finally, Meiner et al. proposed a Topological Transformation Approach to reduce TCAM consumption with two steps. (See, e.g., C. R. Meiners, A. X. Liu and E. Torng, “Topological Transformation Approaches to Optimizing TCAM-Based Packet Classification Systems,” SIGMETRICS, 2009, incorporated herein by reference.) The first step re-encodes and simplifies each field by detecting the equivalent range sections. The second step adjusts each field to alleviate the range expansion problem.
Conceptually, the Dong et al., Liu et al. and Meiner et al. papers all propose field-level schemes, which only focus on each field individually but fail to explore the compression across different fields. In viewing this, McGeer et al. proposed a bit-level solution in their work (See, e.g., R. McGeer and P. Yalagandula, “Minimizing Classifiers for TCAM Implementation,” Proceedings of IEEE INFOCOM, 2009, incorporated herein by reference.) which can yield a higher compression. In McGeer's bit-level solution, the classifier compression problem is treated as a special logic optimization problem with 104 variables, and each rule in the classifier is a product of several variables in Boolean representation or a block in Boolean Space. Therefore, the existing logic optimization techniques can be applied to compress classifiers using the action-oriented property. Moreover, with the first-matching property of TCAM, the compression can be even better.
FIG. 3 is an example illustrating three steps of McGeer's scheme. In the first step, the original classifier 310 (with six rules) is mapped into the Boolean Space shown in the Karnaugh table 320 (See, e.g., Maurice Karnaugh, “The Map Method for Synthesis of Combinational Logic Circuits,” Transactions of the American Institute of Electrical Engineers, part I 72 (9): 593-599, 1953, incorporated herein by reference.) Each rule corresponds to a block (or a point) in the Karnaugh table. During the mapping, the overlapping portion of rules is associated with the action of the highest-priority rule. For example, the point at the up-left corner (i.e. “0000(WXYZ)”), which is covered by both the first and the last rule, is assigned with the action of the first rule (000*). In the second step, classical logic optimization algorithms are applied on the Karnaugh table 320 to merge the neighboring points with the same action to reduce rules. Referring to FIG. 3, “Accept” points are merged and Classifier 1 330 is obtained. In the third step, the first-matching property is applied to Classifier 1 330. Similar to the example described above with reference to FIG. 2(c), an even smaller classifier, which has only three rules (Classifier 2 340) can be obtained. Note that all three classifiers (310, 330 and 340) in the example of FIG. 3 are semantically equivalent since they correspond to the same Karnaugh table 320.
The foregoing classifier compression techniques exploit logic optimization and the first-matching property. Unfortunately, however, the performance of the compression using the foregoing logic optimization and the first-matching property greatly depends on the “rule distribution” of the classifier (e.g., the distributions of rules with action “accept” or “deny” in the Boolean Space). For example, FIGS. 4(a) and 4(b) illustrated two classifiers with different rule distributions. In FIG. 4(a), “rule elements” (a “rule element” is the smallest unit, i.e., a point in the Boolean Space associated with an action) associated with the same action are densely populated. On the other hand, in FIG. 4(b), rule elements are spread sparsely in the Boolean Space. Logic optimization and the first-matching property are very suitable for compressing the densely populated rule distribution in FIG. 4(a). Unfortunately, however, logic optimization and the first-matching property perform poorly under the sparse rule distribution in FIG. 4(b). More specifically, since rule elements in FIG. 4(b) are spread sparsely and no two neighboring rule elements have the same action, no two elements can be directly merged using logic optimization. So under such circumstances, logic optimization cannot contribute much compression. Furthermore the first-matching property cannot contribute much compression. For example, to reduce the number of “Accept” rules using the first-matching property, one would have to create and put many “Deny” rules in the high-priority places (similar to what was done in FIG. 2(c)). This would result in an even larger classifier.
As should be appreciated from the example discussed with reference to FIG. 4(b), it would be useful to be able to compress classifiers having sparse rule distributions. Furthermore, even if a classifier has a rule distribution not as extreme as that in FIG. 4(b), it might have dense rule distributions in some areas, but sparse rule distributions in some other areas. Therefore, it would be useful to be able to compress areas of sparse rule distributions using a new technique, even if know techniques are used to compress areas of dense rule distributions.